template<class T>
T power(T a, long long b) {
	T ret(a.row_, a.col_);
  ret.to_unit();
  assert(a.row_ == a.col_);
	while (b > 0) {
		if (b & 1) {
			ret *= a;
		}
		a *= a;
		b >>= 1;
	}
	return ret;
}

template<class T>
struct Matrix {
	Matrix() {}
	Matrix(int n, int m) {
		row_ = n;
		col_ = m;
		f_.resize(n);
		for (int i = 0; i < n; i++) {
			f_[i].resize(m);
		}
	}

	friend Matrix operator*(const Matrix &lhs, const Matrix &rhs) {
		assert(lhs.col_ == rhs.row_);
		Matrix t(lhs.row_, rhs.col_);

		for (int i = 0; i < lhs.row_; i++) {
			for (int j = 0; j < rhs.col_; j++) {
				for (int k = 0; k < lhs.col_; k++) {
					t.f_[i][j] += lhs.f_[i][k] * rhs.f_[k][j];
				}
			}
		}
		return t;
	}
  Matrix operator*=(const Matrix &rhs) {
		assert(this->col_ == rhs.row_);
		Matrix t(this->row_, rhs.col_);

		for (int i = 0; i < this->row_; i++) {
			for (int j = 0; j < rhs.col_; j++) {
				for (int k = 0; k < this->col_; k++) {
					t.f_[i][j] += this->f_[i][k] * rhs.f_[k][j];
				}
			}
		}
		return *this = t;
	}
  vector<T>& operator[](int index) {
    return f_[index];
  }
  const vector<T>& operator[](int index) const {
    return f_[index];
  }

	void to_unit() {
		assert(row_ == col_);
		for (int i = 0; i < row_; i++) {
			f_[i][i] = 1;
		}
	}

	int col_, row_;
	vector<vector<T>> f_;
};